//给你一个有根节点的二叉树，找到它最深的叶节点的最近公共祖先。 
//
// 回想一下： 
//
// 
// 叶节点 是二叉树中没有子节点的节点 
// 树的根节点的 深度 为 0，如果某一节点的深度为 d，那它的子节点的深度就是 d+1 
// 如果我们假定 A 是一组节点 S 的 最近公共祖先，S 中的每个节点都在以 A 为根节点的子树中，且 A 的深度达到此条件下可能的最大值。 
// 
//
// 
//
// 示例 1： 
//
// 输入：root = [1,2,3]
//输出：[1,2,3]
//解释： 
//最深的叶子是值为 2 和 3 的节点。
//这些叶子的最近共同祖先是值为 1 的节点。
//返回的答案为序列化的 TreeNode 对象（不是数组）"[1,2,3]" 。 
//
// 示例 2： 
//
// 输入：root = [1,2,3,4]
//输出：[4]
// 
//
// 示例 3： 
//
// 输入：root = [1,2,3,4,5]
//输出：[2,4,5]
// 
//
// 
//
// 提示： 
//
// 
// 给你的树中将有 1 到 1000 个节点。 
// 树中每个节点的值都在 1 到 1000 之间。 
// 
// Related Topics 树 深度优先搜索 
// 👍 43 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;

/**
 * Java：最深叶节点的最近公共祖先
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P1123_LowestCommonAncestorOfDeepestLeaves {
    public static void main(String[] args) {
        Solution solution = new P1123_LowestCommonAncestorOfDeepestLeaves().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 自顶向下
     * 左右子树高度相等
     */
    class Solution {
        public TreeNode lcaDeepestLeaves(TreeNode root) {
            if (root == null) {
                return null;
            }
            int left = treeDepth(root.left);
            int right = treeDepth(root.right);
            if (left == right) {
                return root;
            } else if (left > right) {
                return lcaDeepestLeaves(root.left);
            } else {
                return lcaDeepestLeaves(root.right);
            }
        }

        private int treeDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = treeDepth(root.left);
            int right = treeDepth(root.right);
            return 1 + Math.max(left, right);
        }
    }
//    /**
//     * 自底向上
//     * 左右子树高度相等
//     */
//    class Solution {
//        // 公共祖先
//        TreeNode res = null;
//        // 最大深度
//        int maxDepth = -1;
//
//        public TreeNode lcaDeepestLeaves(TreeNode root) {
//            treeDepth(root, 0);
//            return res;
//        }
//
//        private int treeDepth(TreeNode root, int depth) {
//            if (root == null) {
//                return depth;
//            }
//            depth++;
//            int left = treeDepth(root.left, depth);
//            int right = treeDepth(root.right, depth);
//            depth = Math.max(left, right);
//            if (left == right && depth >= maxDepth) {
//                res = root;
//                maxDepth = depth;
//            }
//            return depth;
//
//        }
//    }

    //leetcode submit region end(Prohibit modification and deletion)

}